/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-06-21
 * Time: 22:41
 */

import java.util.*;

//https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8?tpId=13&tqId=587690
//减绳子

//public class Solution {
//    public int cutRope(int n) {
//        //绳子最少为两段，所以必须分出1
//        if (n <= 3) {
//            return n - 1;
//        }
//        // 背包
//        int[] dp = new int[n + 1];
//        //绳子长度小于5的，都可以手动算出最长的一端
//        //大于5的，都是它们的不断组合
//        //从多钟组合中的选出最大的一个
//        dp[1] = 1;
//        dp[2] = 2;
//        dp[3] = 3;
//        dp[4] = 4;
//        for (int i = 5; i <= n; i++) {
//            for (int j = 1; j < i; j++) {
//                dp[i] = Math.max(dp[i], j * dp[i - j]);
//            }
//        }
//        return dp[n];
//    }
//}
import java.util.*;


public class Solution {
    public static void main(String[] args) {
        cutRope(16);
    }
    public static int cutRope (int n) {
        if (n <= 3) {
            return n - 1;
        }
        if (n % 3 == 0) {
            return pow(3, n / 3);
        } else if (n / 3 == 1) {
            return pow(3, n / 3 - 1) * 4;
        } else {
            return pow(3, n / 3) * 2;
        }
    }

    //快速乘法
    public static int fast(int x, int y) {
        int res = 0;
        while (y != 0) {
            if ((y & 1) != 0) {
                res += x;
            }
            x <<= 1;
            y >>= 1;
        }
        return res;
    }

    //快速幂
    public static int pow(int x, int y) {
        int res = 1;
        while (y != 0) {
            if ((y & 1) != 0) {
                res = fast(res, x);
            }
            x = fast(x, x);
            y >>= 1;
        }
        return res;
    }
}